package com.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Search {
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,108,1000,1232};
        System.out.println(fibonacciSearch(arr, 1232));
    }

    /**
     * 顺序查找：逐个比对数组中每一个数，找到返回数组下标
     */
    public static List<Integer> seqSearch(int[] arr, int value){
        ArrayList<Integer> indexList = new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++){
            if(arr[i] == value){
                indexList.add(i);
            }
        }
        return indexList;
    }

    /**
     * 二分查找：查找的数组必须有序，返回查找元素下标
     * 当查找的数组中有重复的数时，将重复的元素下标记录到集合中，返回集合
     */
    public static List<Integer> binarySearch(int[] arr,int left,int right,int findValue){
        int mid = (left + right)/2;
        if(left > right || findValue < arr[0] || findValue >arr[arr.length-1]){
            //return -1;
            return null;
        }
        if(arr[mid] == findValue ){
           // return mid;
            // 1,8,10,89,1000,1000,1232
            //在一个有序集合中，当mid=findValue时，重复的数一定在mid两侧。
            //所以扫描mid两侧，将重复元素下标加入到集合中
            ArrayList<Integer> indexList = new ArrayList<>();
            indexList.add(mid);
            //扫描右侧
            int temp = mid + 1;
            while(findValue == arr[temp] && temp <= right){
                indexList.add(temp);
                temp++;
            }
            temp = mid-1;
            while(findValue == arr[temp] && temp >= left){
                indexList.add(temp);
                temp--;
            }
            return indexList;
        }else if(arr[mid] > findValue){
            return binarySearch(arr,left,mid-1,findValue);
        }else {
            return binarySearch(arr,mid+1,right,findValue);
        }
    }

    /**
     * 插值查找：思路和二分查找一样，改变了mid选取的方式，适用于元素分布比较均匀的有序列表
     */
    public static int insertValueSearch(int[] arr,int left,int right,int findValue){

        if(left > right || findValue < arr[0] || findValue >arr[arr.length-1]){
            //return -1;
            return -1;
        }
        int mid = left + (right-left)* (findValue - arr[left])/(arr[right] -arr[left]);
        if(arr[mid] == findValue ){
            return mid;
        }else if(arr[mid] > findValue){
            return insertValueSearch(arr,left,mid-1,findValue);
        }else {
            return insertValueSearch(arr,mid+1,right,findValue);
        }
    }

    /**
     * 非递归的方式实现斐波那契查找：mid = left + f(k) - 1
     * @param arr
     */
    public static int fibonacciSearch(int arr[],int findValue){
        int low = 0;
        int hight = arr.length-1;
        //表示斐波那契分割数的下标
        int k = 0;
        int mid = 0;
        int f[] = fib();
        //找到一个k使得f[k]-1大于或等于顺序表中元素个数，大于时用最后一个元素进行扩充
        while(f[k] - 1 < hight){
            k++;
        }
        //Arrays.copyof(原始数组，新数组的长度)
        int[] temp = Arrays.copyOf(arr,f[k]);
        for(int i = hight+1; i <temp.length;i++){
            temp[i] = arr[hight];
        }

        while(low <= hight){
            mid = low + f[k-1]-1;
            //因为f[k]=f[k-1]+f[k-2]
            //temp[mid]>findValue,表示代查找的元素在f[k-1]这部分，所以重新定位mid前，令hight = mid -1 , k-1
            //temp[mid]<findValue,表示代查找的元素在f[k-2]这部分，所以重新定位mid前，令low = mid + 1 , k-2
            if(temp[mid] > findValue){
                hight = mid -1;
                k--;
            }else if(temp[mid] < findValue){
                low = mid +1;
                k -= 2;
            }else {
                //表示已经找到元素位置
                if(mid <= hight){
                    return mid;
                }else {
                    //查找的下标mid落在扩充的元素中，即最后一个元素
                    return hight;
                }
            }
        }
        return -1;
    }

    /**
     * 创建斐波那契数列
     * @return
     */
    public static int[] fib(){
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for(int i = 2;i<20;i++){
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }
}
